package com.example.springbootexamples.datastructure;

import com.example.springbootexamples.domain.Node;
import org.junit.Test;

import java.util.*;

public class TreeDemo {

    @Test
    public void t(){
        List<Node> nodes=new ArrayList<>();
        nodes.add(new Node("1",null,"1"));
        nodes.add(new Node("2","1","1"));
        nodes.add(new Node("3","1","1"));
        nodes.add(new Node("4","3","1"));
        nodes.add(new Node("5","4","1"));
        nodes.add(new Node("6","5","1"));
        createTree(nodes);

        Node root=getRoot(nodes);
        traverse(root);
        List<Node> flatList=new ArrayList<>();
        List<Node> flatIterList=new ArrayList<>();
        flat(root,flatList);
        System.out.println("a");
        flatIter(root,flatIterList);
        System.out.println("a");
    }
    List<Node> flat(Node root){
        List<Node> nodes=new ArrayList<>();
        if(root!=null){
            nodes.add(root);

        }
        return nodes;
    }

    void flat(Node node,List<Node> nodes){
        if(node!=null){
            nodes.add(node);
            if(node.getChild()!=null){
                for(Node n:node.getChild()){
                    flat(n,nodes);
                }
            }
        }
    }

    void flatIter(Node root,List<Node> nodes){

        Deque<Node> deque=new ArrayDeque<>();
        deque.add(root);
        while(!deque.isEmpty()){
            Node n=deque.removeLast();
            nodes.add(n);
            List<Node> child=n.getChild();
            if(child!=null){
                deque.addAll(child);
            }

        }

    }

    void createTree(List<Node> nodes){
        Map<String,Node> map=new HashMap<>();
        for(Node node:nodes){
            map.put(node.getId(),node);
        }

        for(Node node:nodes){
            String pid=node.getPid();
            if(pid!=null){
                Node p=map.get(pid);
                if(p!=null){
                    node.setParent(p);
                    List<Node> child=p.getChild();
                    child.add(node);
                }
            }
        }
    }

    void traverse(Node node){
        if(node!=null){
            System.out.println(node.getId());
            if(node.getChild()!=null)
            for(Node n:node.getChild()){

                traverse(n);
            }
        }
    }

    Node getRoot(List<Node> nodes){
        for(Node node:nodes){
            if(node.getParent()==null){
                return node;
            }
        }
        return null;
    }


}
